The present invention relates generally to data communication systems and more particularly relates to a soft decision decoder suitable for use in a code shift keying based direct sequence spread spectrum communication system.
In recent years, the world has witnessed explosive growth in the demand for communications and networking and it is predicted that this demand will increase in the future. Many communication and networking schemes utilize some form of error correcting techniques to correct errors caused during transmission over noisy, non-ideal communication channels. The use of error detection and correcting codes has thus been widely used in various communications fields in order to improve the reliability of data transmission. In particular, a well-known class of error correcting code (ECC) schemes includes block codes and decoders that perform maximum likelihood detection decoding.
A block diagram illustrating a generalized digital communication system is shown in FIG. 1. The general digital communication system, generally referenced 10, comprises a transmitter 12 and receiver 14 connected via a channel 20. The data arrives at a rate of one bit every Ts seconds and is stored until a block of K bits accumulates. The block is then input to the encoder 16 as one of M possible messages denoted H1, H2, . . . , HM where M=2K. The encoder performs a mapping from the input message to a signal xm. The modulator 18 converts the signal xm to a signal of finite duration T=KTS. Thus, a set of messages {Hm} is mapped to a set of signals {xm(t)}.
The goal of the channel encoder 16 is to perform a mapping from an input digital sequence to a channel input sequence and the goal of the channel decoder 24 is to perform a mapping from the channel output sequence to an output digital sequence. The encoder and decoder should be constructed so as to minimize the effect of channel noise, i.e. the differences between input and output digital sequences are minimized. In order to achieve this, redundancy is introduced in the channel encoder that is subsequently used by the decoder to reconstruct the input sequence as accurately as possible.
The signals are transmitted onto the channel 20 and received as y(t) at the receiver 14. The receiver comprises a demodulator 22 and decoder 24. In particular, the goal of the decoder is to perform a mapping from the vector y to a decision H{circumflex over (m)} on the message transmitted. A suitable criterion for this decision is to minimize the probability of error of the decision. The optimum decision rule, given the criterion is to minimize the error probability in mapping each vector y to a decision, can be expressed as
H{circumflex over (m)}=Hm if Pr(Hmsent|y)xe2x89xa7Pr(Hmxe2x80x2sent|y) for all mxe2x80x2xe2x89xa0mxe2x80x83xe2x80x83(1)
The above condition can be expressed in terms of prior probabilities of the messages and in terms of the conditional probabilities of y given each Hm that are called the likelihood functions. The optimum decision in Equation 1 can be expressed, using Bayes"" rule, as                               H                      m            ^                          =                                                            H                m                            ⁢                              xe2x80x83                            ⁢              if              ⁢                              xe2x80x83                            ⁢              ln              ⁢                              xe2x80x83                            ⁢                              π                m                                      +                                          ∑                                  n                  =                  1                                N                            ⁢                              xe2x80x83                            ⁢                              ln                ⁢                                  xe2x80x83                                ⁢                                  p                  ⁡                                      (                                                                  y                        n                                            ❘                                              x                        mn                                                              )                                                                                 greater than                                     ln              ⁢                              xe2x80x83                            ⁢                              π                                  m                  xe2x80x2                                                      +                                          ∑                                  n                  =                  1                                N                            ⁢                              ln                ⁢                                  xe2x80x83                                ⁢                                  p                  ⁡                                      (                                                                  y                        n                                            ❘                                              x                                                                              m                            xe2x80x2                                                    ⁢                          n                                                                                      )                                                  ⁢                                  xe2x80x83                                ⁢                for                ⁢                                  xe2x80x83                                ⁢                all                ⁢                                  xe2x80x83                                ⁢                                  m                  xe2x80x2                                                              ≠          m                                    (        2        )            
where xmn represents the nth component (i.e. an individual bit) of the mth vector. Thus, the goal is the choose the output decision (i.e. codeword Hm) that yields a maximum.
In most cases, the message probabilities are all equal,thus                                           π            m                    =                                                    1                M                            ⁢                              xe2x80x83                            ⁢              m                        =            1                          ,        2        ,        …        ⁢                  xe2x80x83                ,        M                            (        3        )            
Therefore the factors xcfx80m, xcfx80mxe2x80x2 can be eliminated from Equation 2. The resulting decision rule is then referred to as maximum likelihood. The maximum likelihood decoder depends only on the channel. Note that the logarithm of the likelihood function is commonly used as the metric. The maximum likelihood decoder thus functions to compute the metrics for each possible signal vector, compare them and decide in favor of the maximum.
Additional background information on coding and digital communications can be found in the book xe2x80x9cPrinciples of Digital Communication and Coding,xe2x80x9d A. J. Viterbi and J. K. Omura, McGraw Hill, Inc., 1979.
Soft decision decoding techniques are known in the art. Examples of well-known codes include Tornado code, Hamming code, Convolution Code, Turbo Code, Reed-Solomon Code and Arithmetic Code. The Hamming Code is a family of optimal binary (2nxe2x88x921, 2nxe2x88x921xe2x88x92n) codes that is capable of correcting one error or three erasures. A disadvantage of this code is that it is a binary code and thus cannot take advantage of multi-bit symbol constellations associated with symbol codes. The convolution code is one of the best known soft decision codes that can be decoded using a Viterbi algorithm. A disadvantage of this code is that it is complex to implement in hardware and is not as effective for high code rates close to one.
Turbo codes (or parallel concatenated convolution codes) are more complex than convolution codes but provide better performance. Disadvantages of this code include relatively long decoding delays (i.e. very long codewords), complex decoding algorithm with large memory requirements and the fact that the code is a binary code and not a symbol code.
The Reed-Solomon code is a special case of the block Hamming Code. It is a symbol code (2xe2x88x921, 2nxe2x88x921xe2x88x922t) capable of t error or 2t erasure corrections. A disadvantage in realizing this type of coder/decoder is the large amount of hardware required. In addition, it is relatively difficult to perform soft decision decoding with Reed Solomon codes.
Another well known coding technique is Wagner coding, in which encoding is performed by appending a single parity check bit to a block of k information bits. Upon reception of each received digit ri, the a posteriori probabilities p(0|ri) and p(1|ri) are calculated and saved, and a hard bit decision is made on each of the k+1 digits. Parity is checked, and if satisfied, the k information bits are accepted. If parity fails, however, the received digit having the smallest different between its two a posteriori probabilities is inverted before the k information bits are accepted. In this case, a single erasure may be filled but no errors can be corrected.
A generalization of the Wagner coding technique applicable to any multiple error correcting (n, k) code is a scheme known as forced erasure decoding. The receiver, using such a scheme, makes a hard binary decision on each received bit as well as measures relative reliability. Note that in many communication systems, the probability of correct bit demodulation and decoding is monotonically related to the magnitude of the detected signal, i.e. the detected signal strength is a measure of bit reliability.
A disadvantage of the prior art soft decision decoding techniques is that they are intended for blocks of information made up of bits and not symbols. In addition, most require very large gate counts in order to realize the hardware circuitry needed to implement the code.
Accordingly, it is a general object of the present invention to provide a novel and useful soft decision maximum likelihood detection method, in which the problems described above are eliminated. The present invention comprises an encoder and decoder for a forward error correcting code. The decoding technique of the present invention utilizes soft decision maximum likelihood decoding that is especially suited for codes that operate on symbols rather than bits and is particularly well suited for short blocks, e.g., blocks consisting of tens of symbols.
The present invention comprises a decoding technique that utilizes a maximum likelihood function in combination with an erasure correcting coding scheme to correct multiple errors in a block. Note that in coding theory terminology, an erasure is an error whose location is known. The erasure correcting codes used with the decoding method of the present invention, are operative to correct b erasures in a receive block of length n symbols. The decoding method of the present invention is capable of correcting b+1 errors using any arbitrary code that is capable of correcting b erasures. The decoding method can correct more errors than erasures due to the use of additional information regarding the reliability of the received symbols together the with the hard decisions.
Any suitable erasure/error correcting code may be used with the decoding method of the present invention. Two example embodiments are provided, one that utilizes the Soft Diagonal Parity (SDP) code and another that utilizes the Even Odd Parity (EOP) code. The SDP code is capable of correcting a single erasure while the EOP code is capable of correcting two erasures. The method of encoding the soft decision error correcting code for both the SDP and EOP codes are also described.
The decoding method can be used with any modulation scheme that can provide likelihood values for all possible symbol values for each received symbol. In the case where the modulation scheme used comprises Code Shift Keying (CSK), the likelihood values provided by the receiver comprise correlation values and the symbol values comprise shift indexes. The receiver also provides the hard decisions (i.e. the index yielding the maximum correlation).
First, the (b+1)th error is corrected by assuming a certain value in each symbol location. Then, for each symbol in a codewords, all valid symbol possibilities are tested. For each symbol possibility, the metric of the resulting codeword is calculated using the likelihoods provided by the receiver. The remaining b errors are corrected by assuming erasures in all possible combinations of b symbols. For each combination of symbols, the b symbols are marked as erasures and corrected using the desired erasure correcting code, e.g., SDP, EOP, etc. The metric of the resulting codeword is also calculated. The codeword yielding the maximum metric (i.e. the codeword most likely to have been received) is selected and subsequently decoded and output.
There is thus provided in accordance with the present invention a method of soft decoding capable of correcting b+1 errors using a block erasure correcting code with the ability to correct b erasures, the method comprising the steps of receiving for each symbol in a block of n symbols, a set of symbol metrics wherein each possible symbol value has a metric associated therewith, and a hard decision metric, looping through all symbols in the block, and for each symbol, assuming the symbol is in error, testing K possible symbol values looping through all possible combinations of b symbols from among the remaining symbols, and for each combination of b symbols, marking the combination as erasures, correcting the erasures using the erasure correcting code, calculating the likelihood of the resulting codeword, selecting the codeword having a maximum likelihood associated therewith and wherein n, K and b are positive integers.
There is also provided in accordance with the present invention a full information set soft decision decoder for correcting b+1 errors using a block erasure correcting code with the ability to correct b erasures comprising a receiving mechanism for each symbol in a block of n symbols, a set of likelihoods wherein each possible symbol value has a likelihood associated therewith, and a hard decision equal to the symbol value corresponding to a maximum likelihood, a converter for converting the correlation values to log probability ratios, an erasure generator adapted to generate all possible combinations of erasure patterns, an erasure correction decoder adapted to correct the block in accordance with each erasure pattern generated, a likelihood generator for calculating the likelihood of the resulting codeword corresponding to each possible combination of erasure pattern, search means for determining the codeword yielding a maximum likelihood and a decoder mechanism operative to decode the codeword corresponding to a maximum likelihood.
There is further provided in accordance with the present invention a method of soft decoding capable of correcting b+1 errors using a block erasure correcting code with the ability to correct b erasures, the method comprising the steps of receiving a hard decision metric and a set of symbol metrics comprising a metric for each possible symbol value, assuming a single error in each symbol location, and for each symbol, calculating a first metric difference between the metric for a first trial symbol and the hard decision metric, assuming b erasures in the symbol, and for each of the b symbols, correcting the erasures using the erasure correcting code, calculating a second metric difference between the metric for a second trial symbol and the hard decision metric, summing the second method differences and the first metric difference to yield a sum of differences, selecting the codeword yielding a minimum sum of differences and wherein b is as positive integer.
In accordance with the present invention, there is also provided a method of generating a soft decision error correcting code, the method comprising the steps of initializing a parity symbol, receiving a block of data comprising nxe2x88x921 symbols, and for each symbol, XORing the symbol with the parity symbol, rotating the parity symbol, including the resultant parity symbol as the nth symbol in the block and wherein n is a positive integer.
There is further provided in accordance with the present invention a method of generating a soft decision error correcting code, the method comprising the steps of initializing a horizontal parity symbol, initializing a diagonal parity symbol, receiving a block of data comprising a plurality of symbols, and for each symbol, XORing the symbol with the horizontal parity symbol, XORing the symbol with the diagonal parity symbol, rotating the diagonal parity symbol, calculating an xe2x80x98Sxe2x80x99 bit from the data block, setting the diagonal parity symbol in accordance with the xe2x80x98Sxe2x80x99 bit, appending the resultant horizontal parity symbol to the block and appending the resultant diagonal parity symbol to the block.
There is also provided in accordance with the present invention a communication apparatus coupled to channel comprising an encoder adapted to generate a soft decision code from a block of data received from a data source, a transmitter operative to transmit data including the soft decision code over the channel, a receiver operative to receive data from the communications channel and to generate a set of soft symbol metrics and a hard symbol metric for each symbol received, a soft decoder adapted to decode the received data so as to yield the original transmitted symbols, the soft decoder operative to receive the hard decision metric and the set of symbol metrics, assume a single error in each symbol location, and for each symbol, calculate a first metric difference between the metric for a first trial symbol and the hard decision metric, assume one or more erasures in the symbol, and for erased symbol, correct the erasures using the erasure correcting code, calculate a second metric difference between the metric for a second trial symbol and the hard decision metric, sum the second method differences and the first metric difference to yield a sum of differences and select the codeword yielding a minimum sum of differences.
There is thus provided in accordance with the present invention a method of soft decoding capable of correcting b+1 errors using a block erasure correcting code with the ability to correct b erasures, the method comprising the steps of receiving for each symbol in a block of n symbols, a set of symbol metrics wherein each possible symbol value has a metric associated therewith, and a hard decision metric, looping through all symbols in the block, and for each symbol, assuming the symbol is in error, testing K possible symbol values looping through all possible combinations of b symbols from among the remaining symbols, and for each combination of b symbols, marking the combination as erasures, correcting the erasures using the erasure correcting code, calculating the likelihood of the resulting codeword, selecting the codeword having a maximum likelihood associated therewith and wherein n, K and b are positive integers.
There is also provided in accordance with the present invention a full information set soft decision decoder for correcting b+1 errors using a block erasure correcting code with the ability to correct b erasures comprising a receiving mechanism for each symbol in a block of n symbols, a set of likelihoods wherein each possible symbol value has a likelihood associated therewith, and a hard decision equal to the symbol value corresponding to a maximum likelihood, a converter for converting the correlation values to log probability ratios, an erasure generator adapted to generate all possible combinations of erasure patterns, an erasure correction decoder adapted to correct the block in accordance with each erasure pattern generated, a likelihood generator for calculating the likelihood of the resulting codeword corresponding to each possible combination of erasure pattern, search means for determining the codeword yielding a maximum likelihood and a decoder mechanism operative to decode the codeword corresponding to a maximum likelihood.
There is further provided in accordance with the present invention a method of soft decoding capable of correcting b+1 errors using a block erasure correcting code with the ability to correct b erasures, the method comprising the steps of receiving a hard decision metric and a set of symbol metrics comprising a metric for each possible symbol value, assuming a single error in each symbol location; and for each symbol, calculating a first metric difference between the metric for a first trial symbol and the hard decision metric, assuming b erasures in the symbol; and for each of the b symbols, correcting the erasures using the erasure correcting code, calculating a second metric difference between the metric for a second trial symbol and the hard decision metric, summing the second method differences and the first metric difference to yield a sum of differences, selecting the codeword yielding a minimum sum of differences and wherein b is as positive integer.
There is still further provided in accordance with the present invention a method of generating a soft decision error correcting code, the method comprising the steps of initializing a parity symbol, receiving a block of data comprising nxe2x88x921 symbols; and for each symbol, XORing the symbol with the parity symbol, rotating the parity symbol, including the resultant parity symbol as the nth symbol in the block and wherein n is a positive integer.
There is also provided in accordance with the present invention a method of generating a soft decision error correcting code, the method comprising the steps of initializing a horizontal parity symbol, initializing a diagonal parity symbol, receiving a block of data comprising a plurality of symbols; and for each symbol, XORing the symbol with the horizontal parity symbol, XORing the symbol with the diagonal parity symbol, rotating the diagonal parity symbol, calculating an xe2x80x98Sxe2x80x99 bit from the data block, setting the diagonal parity symbol in accordance with the xe2x80x98Sxe2x80x99 bit, appending the resultant horizontal parity symbol to the block and appending the resultant diagonal parity symbol to the block.
In addition, there is provided in accordance with the present invention a communication apparatus coupled to channel comprising an encoder adapted to generate a soft decision code from a block of data received from a data source, a transmitter operative to transmit data including the soft decision code over the channel, a receiver operative to receive data from the communications channel and to generate a set of soft symbol metrics and a hard symbol metric for each symbol received, a soft decoder adapted to decode the received data so as to yield the original transmitted symbols, the soft decoder operative to receive the hard decision metric and the set of symbol metrics, assume a single error in each symbol location; and for each symbol, calculate a first metric difference between the metric for a first trial symbol and the hard decision metric, assume one or more erasures in the symbol; and for an erased symbol, correct the erasures using the erasure correcting code, calculate a second metric difference between the metric for a second trial symbol and the hard decision metric, sum the second method differences and the first metric difference to yield a sum of differences and select the codeword yielding a minimum sum of differences.